{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Numbers With Units Digit K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #math #dynamic-programming #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数学 #动态规划 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumNumbers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #个位数字为 K 的整数之和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数 <code>num</code> 和 <code>k</code> ，考虑具有以下属性的正整数多重集：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>每个整数个位数字都是 <code>k</code> 。</li>\n",
    "\t<li>所有整数之和是 <code>num</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回该多重集的最小大小，如果不存在这样的多重集，返回<em> </em><code>-1</code> 。</p>\n",
    "\n",
    "<p>注意：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>多重集与集合类似，但多重集可以包含多个同一整数，空多重集的和为 <code>0</code> 。</li>\n",
    "\t<li><strong>个位数字</strong> 是数字最右边的数位。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 58, k = 9\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>\n",
    "多重集 [9,49] 满足题目条件，和为 58 且每个整数的个位数字是 9 。\n",
    "另一个满足条件的多重集是 [19,39] 。\n",
    "可以证明 2 是满足题目条件的多重集的最小长度。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 37, k = 2\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>个位数字为 2 的整数无法相加得到 37 。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>num = 0, k = 7\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>空多重集的和为 0 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= num &lt;= 3000</code></li>\n",
    "\t<li><code>0 &lt;= k &lt;= 9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-numbers-with-units-digit-k](https://leetcode.cn/problems/sum-of-numbers-with-units-digit-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-numbers-with-units-digit-k](https://leetcode.cn/problems/sum-of-numbers-with-units-digit-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['58\\n9', '37\\n2', '0\\n7']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        # if num < k:\n",
    "        #     return -1\n",
    "        target = num % 10\n",
    "        for i in range(1,11):\n",
    "            if i * k % 10 == target and num >= i * k:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        for i in range(1, 11):\n",
    "            if k*i<=num and (num-k*i)%10 ==0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if not num:\n",
    "            return 0\n",
    "        target = str(num)[-1]\n",
    "        step = 1\n",
    "        res = -1\n",
    "        while step <= 10:\n",
    "            cur = step * k\n",
    "            s = str(cur)[-1]\n",
    "            if s == target:\n",
    "                res = step\n",
    "                break\n",
    "            step += 1\n",
    "        if res * k <= num:\n",
    "            return res\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if num < k:\n",
    "            return -1\n",
    "        target = num % 10\n",
    "        for i in range(1,11):\n",
    "            if i * k % 10 == target and num >= i * k:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        for i in range(1, 11):\n",
    "            if i * k <= num and (num - i * k) % 10 == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(1, 11):\n",
    "            if k * i <= num and (num - k * i) % 10 == 0:\n",
    "                return i\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1 if num%10 != 0 else 1\n",
    "        ret = 1\n",
    "        while ret <= 10 and ret * k <= num and ret*k % 10 != num % 10:\n",
    "            ret += 1\n",
    "        if ret != 11 and ret * k <= num:\n",
    "            return ret\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "\n",
    "        ans = k\n",
    "\n",
    "        if num == 0:\n",
    "            return 0\n",
    "            \n",
    "        for i in range(1,11):\n",
    "            if ans%10 == num%10 and ans <= num:\n",
    "                return i\n",
    "            ans+=k\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        for i in range(1, 11):\n",
    "            if k * i <= num and (num - k * i) % 10 == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:return 0\n",
    "        # 答案最少0个，最多num个，从1到num遍历\n",
    "        # 把每个数看成是10*mi + k，如果存在满足题意，则和为10*Σi:1~num(mi)+i*k，那么只要num-i*k是10的倍数，也就一定能找到一组自然数mi满足等式：num = 10*Σi:1~num(mi)+i*k\n",
    "        res = 0\n",
    "        for i in range(1,num+1):\n",
    "            if num-i*k>=0 and (num-i*k)%10==0:return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        for i in range(1, num + 1):\n",
    "            if num - i * k < 0: break\n",
    "            if (num - i * k) % 10 == 0:\n",
    "                return i \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        t = num%10\n",
    "        for i in range(1,11):\n",
    "            if num-i*k<0:\n",
    "                return -1\n",
    "            if t==(i*k)%10:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1 if num%10 != 0 else 1\n",
    "        ret = 1\n",
    "        while ret * k <= num and ret*k % 10 != num % 10:\n",
    "            ret += 1\n",
    "        if ret * k <= num:\n",
    "            return ret\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        for n in range(1, num + 1):\n",
    "            if num - n * k < 0: break\n",
    "            if (num - n * k) % 10 == 0: return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num, k):\n",
    "        if num == 0: return 0\n",
    "        if k == 0: return -1 if num % 10 else 1\n",
    "        return next((n for n in range(1, min(num // k + 1, 11)) if ((num - n * k) % 10 == 0)), -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        temp = num%10\n",
    "        n = 0\n",
    "        for i in range(1,11):\n",
    "            if k*i%10 == temp:\n",
    "                n = i\n",
    "                break\n",
    "        return n if n>0 and num-k*n >= 0 else -1 \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MANTISSA = ((0,), \n",
    "            (1, 2, 3, 4, 5, 6, 7, 8, 9, 0),\n",
    "            (2, 4, 6, 8, 0),\n",
    "            (3, 6, 9, 2, 5 ,8, 1, 4, 7, 0),\n",
    "            (4, 8, 2, 6, 0),\n",
    "            (5, 0),\n",
    "            (6, 2, 8, 4, 0),\n",
    "            (7, 4, 1, 8, 5, 2, 9, 6, 3, 0),\n",
    "            (8, 6, 4, 2, 0),\n",
    "            (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)\n",
    "            )\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        # 只有3、7、9可以获得所有尾数\n",
    "        last = num % 10\n",
    "        if last not in MANTISSA[k]:\n",
    "            return -1\n",
    "        time = MANTISSA[k].index(last) + 1\n",
    "        if k * time > num:\n",
    "            return -1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MANTISSA = ((0,), \n",
    "            (1, 2, 3, 4, 5, 6, 7, 8, 9, 0),\n",
    "            (2, 4, 6, 8, 0),\n",
    "            (3, 6, 9, 2, 5 ,8, 1, 4, 7, 0),\n",
    "            (4, 8, 2, 6, 0),\n",
    "            (5, 0),\n",
    "            (6, 2, 8, 4, 0),\n",
    "            (7, 4, 1, 8, 5, 2, 9, 6, 3, 0),\n",
    "            (8, 6, 4, 2, 0),\n",
    "            (9, 8, 7, 6, 5, 4, 3, 2, 1, 0)\n",
    "            )\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        # 只有3、7、9可以获得所有尾数\n",
    "        last = num % 10\n",
    "        if last not in MANTISSA[k]:\n",
    "            return -1\n",
    "        time = MANTISSA[k].index(last) + 1\n",
    "        if k * time > num:\n",
    "            return -1\n",
    "        return time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        table = {}\n",
    "        t = k\n",
    "        ans = 0\n",
    "        while t not in table:\n",
    "            ans +=1\n",
    "            table[t] = ans\n",
    "            t = (t+k)%10\n",
    "        n = num%10\n",
    "        if n not in table:\n",
    "            return -1\n",
    "        if num<table[n]*k:\n",
    "            return -1\n",
    "        #print(table)\n",
    "        return table[n]\n",
    "        print(table)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0 :\n",
    "            return 0\n",
    "        for i in range(1, num + 1):\n",
    "            s = i * k\n",
    "            if num < s:\n",
    "                break\n",
    "            if s % 10 == num % 10:\n",
    "                return i\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1 if num%10 != 0 else 1\n",
    "        ret = 1\n",
    "        while ret <= 10 and ret * k <= num and ret*k % 10 != num % 10:\n",
    "            ret += 1\n",
    "        if ret != 11 and ret * k <= num:\n",
    "            return ret\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        for i in range(1,11):\n",
    "            num -= k\n",
    "            if num >= 0 and num % 10 == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1 if num%10 != 0 else 1\n",
    "        ret = 1\n",
    "        while ret * k <= num and ret*k % 10 != num % 10:\n",
    "            ret += 1\n",
    "        if ret * k <= num:\n",
    "            return ret\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1 if num % 10 else 1\n",
    "        for i in range(1, num // k + 1):\n",
    "            left = num - i * k     \n",
    "            if left % 10 == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        target = num % 10\n",
    "        cur = k\n",
    "        cnt = 1\n",
    "        while cur != target:\n",
    "            cur += k\n",
    "            cur %= 10\n",
    "            cnt += 1\n",
    "            if cur == k:\n",
    "                break\n",
    "        if cur == target and num >= k * cnt:\n",
    "            return cnt\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1 if num%10 != 0 else 1\n",
    "        ret = 1\n",
    "        while ret <= 10 and ret * k <= num and ret*k % 10 != num % 10:\n",
    "            ret += 1\n",
    "        if ret != 11 and ret * k <= num:\n",
    "            return ret\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        for n in range(1, num + 1):\n",
    "            if num - n * k < 0: break\n",
    "            if (num - n * k) % 10 == 0: return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        for i in range(1, 11):\n",
    "            if k * i <= num and (num - k * i) % 10 == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0: return 0\n",
    "        for i in range(1, 11):\n",
    "            if k*i<=num and (num-k*i)%10==0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        for i in range(1, 11):\n",
    "            if k * i <= num :\n",
    "                if (num - k * i) % 10 == 0:\n",
    "                    return i\n",
    "            else:\n",
    "                return -1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        if k == 0: return -1 if num % 10 else 1\n",
    "        return next((n for n in range(1, num // k + 1) if (num - n * k) % 10 == 0), -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num, k):\n",
    "        if num == 0: return 0\n",
    "        if k == 0: return -1 if num % 10 else 1\n",
    "        return next((n for n in range(1, min(num // k + 1, 11)) if ((num - n * k) % 10 == 0)), -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        # 完全背包问题,表示大小为i的和最多由几个组成\n",
    "        dp = [inf]*(num+1)\n",
    "        dp[0] = 0\n",
    "\n",
    "        i = 0\n",
    "        while 10*i+k <= num:\n",
    "            for j in range(1,num+1):\n",
    "                if j >= 10*i+k:\n",
    "                    dp[j] = min(dp[j],dp[j-10*i-k]+1) \n",
    "            i+=1\n",
    "        if dp[-1] != inf:\n",
    "            return dp[-1]\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        for i in range(1, 11):\n",
    "            if (num - i * k) % 10 == 0 and num >= i * k:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        # if num == 0:\n",
    "        #     return 0\n",
    "        # if k == 0: return -1 if num % 10 else 1\n",
    "        # return next((n for n in range(1, min(num // k +1, 11)) if ((num - n * k) % 10 == 0)), -1)\n",
    "\n",
    "        if num == 0: return 0 \n",
    "        for n in range(1, num+1):\n",
    "            if num - n * k < 0: break\n",
    "            if (num - n * k) % 10 == 0: return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        \n",
    "        for cnt in range(10):\n",
    "            if num >= (cnt + 1) * k and (num - (cnt + 1) * k) % 10 == 0:\n",
    "                return cnt + 1\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        for i in range(1, 11):\n",
    "            if k * i <= num :\n",
    "                if (num - k * i) % 10 == 0:\n",
    "                    return i\n",
    "            else:\n",
    "                return -1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0 \n",
    "        for i in range(1, num + 1):\n",
    "            if num - i * k < 0:\n",
    "                break \n",
    "            elif (num - i * k) % 10 == 0:\n",
    "                return i \n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        for n in range(1, num + 1):\n",
    "            if num - n * k < 0: break\n",
    "            if (num - n * k) % 10 == 0: return n\n",
    "        return -1\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/sum-of-numbers-with-units-digit-k/description/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return 1 if num % 10 == 0 else -1\n",
    "        \n",
    "        for i in range(1, 1 + num // k):\n",
    "            if (i * k) % 10 == num % 10:\n",
    "                return i\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0:\n",
    "            return 0\n",
    "        for i in range(1,11):\n",
    "            if i*k%10==num%10 and i*k<=num:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        num_map = {}\n",
    "        for i in range(1,11):\n",
    "            mantissa = i*k%10\n",
    "            if mantissa not in num_map:\n",
    "                num_map[mantissa] = i\n",
    "\n",
    "        num_mantissa = num%10\n",
    "        if num_mantissa not in num_map:\n",
    "            return -1\n",
    "        less_num = num_map[num_mantissa] * k\n",
    "        if num < less_num:\n",
    "            return -1\n",
    "\n",
    "        return num_map[num_mantissa]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        end = num%10\n",
    "        for i in range(1, 11):\n",
    "            if i*k%10 == end:\n",
    "                if num >= i*k:\n",
    "                    return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        \n",
    "        for i in range(1, 11):\n",
    "            if k * i <= num and (num - k * i) % 10 == 0:\n",
    "                return i\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "\n",
    "        for n in range(1, num + 1):\n",
    "            if (num - n * k) < 0: return -1\n",
    "            if (num - n * k) % 10 == 0: return n\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num==0 :\n",
    "            return 0\n",
    "        if k==0 and num%10!=0:\n",
    "            return -1\n",
    "        for i in count(1):\n",
    "            if k*i%10==num%10 and k*i<=num:\n",
    "                return i \n",
    "            if k*i>num:\n",
    "                return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        for n in range(1, num + 1):\n",
    "            if num - n * k < 0: break\n",
    "            if (num - n * k) % 10 == 0: return n\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "\n",
    "        if num%2 != 0 and (k%2) ==0:\n",
    "            return -1\n",
    "        yu = num%10\n",
    "\n",
    "        for cnt in range(1,11):\n",
    "            if cnt*k%10 == yu and cnt*k<=num:\n",
    "                return cnt\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0: return 0\n",
    "        if k == 0:\n",
    "            if num % 10 == 0:\n",
    "                return 1\n",
    "            return -1\n",
    "        deo = num - num % 10 + k\n",
    "        deo = deo if deo <= num else deo-10\n",
    "        while deo > 0:\n",
    "            x = num - deo\n",
    "            if x % k == 0:\n",
    "                return x // k + 1\n",
    "            deo -= 10\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        for x in range(1, num+1):\n",
    "            if (num - k*x) < 0:\n",
    "                return -1\n",
    "            if (num - k*x) % 10 == 0 :\n",
    "                return x\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        # 观察nk被的末尾是否为num的末尾，且nk<=num,则返回n,否则返回-1\n",
    "        # 如果末尾数组重复出现了，说明循环了则永不可能\n",
    "        if num==0:return 0\n",
    "        d=num%10\n",
    "        seen=set()\n",
    "        cnt=1\n",
    "        while cnt*k%10 not in seen:\n",
    "            if cnt*k%10==d and cnt*k<=num:\n",
    "                return cnt \n",
    "            seen.add(cnt*k%10)\n",
    "            cnt+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        if num == 0:\n",
    "            return 0\n",
    "        temp = num\n",
    "        t = 0\n",
    "        while (temp % 10 != 0 and t <= 10) or t == 0:\n",
    "            temp -= k\n",
    "            t += 1\n",
    "\n",
    "        if t > 10 or num < t*k:\n",
    "            return -1\n",
    "        else:\n",
    "            return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        dp = [inf]*(num+1)\n",
    "        dp[0] = 0\n",
    "        for x in range(1, num+1):\n",
    "            if x % 10 == k:\n",
    "                for i in range(x, num+1):\n",
    "                    if dp[i-x]+1<dp[i]:\n",
    "                        dp[i] = dp[i-x]+1\n",
    "        ans = dp[-1]\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumNumbers(self, num: int, k: int) -> int:\n",
    "        ans = 0\n",
    "        if not num:\n",
    "            return ans\n",
    "        if not k:\n",
    "            return 1 if not num % 10 else -1\n",
    "        def dfs(nums,m,n):\n",
    "            if nums % 10 == m:\n",
    "                return n + 1\n",
    "            if nums <= 10:\n",
    "                if not nums % k:\n",
    "                    return n + (nums // k)\n",
    "                else:\n",
    "                    return -1\n",
    "            return dfs(nums-m, m, n+1)\n",
    "        ans = dfs(num, k, 0)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
